T-Theory Applications to Online Algorithms for the Server Problem

摘要

Although largely unnoticed by the online algorithms community, T-theory, afield of discrete mathematics, has contributed to the development of severalonline algorithms for the k-server problem. A brief summary of the k-serverproblem, and some important application concepts of T-theory, are given.Additionally, a number of known k-server results are restated using theestablished terminology of T-theory. Lastly, a previously unpublished3-competitiveness proof, using T-theory, for the Harmonic algorithm for twoservers is presented.